//求第n个斐波那契数列的值
//解法1.递归
//当n很大时，时间复杂度很大O（2^n），且可能导致栈溢出
#include<iostream>
using namespace std;
class Solution
{
public:
	int Fibonacci(int n)
	{
		if (n == 0)
			return 0;
		if (n == 1 || n == 2)
			return 1;
		val= Fibonacci(n - 1) + Fibonacci(n - 2);
		return val;
	}
	void Print()const
	{
		cout << val << endl;
	}
private:
	size_t val;
};
int main()
{
	Solution fib;
	fib.Fibonacci(45);
	fib.Print();
	return 0;
}
